//
// Created by Administrator on 2021/12/31.
//

#ifndef CPP_LEARNING_BIN_TREE_HPP
#define CPP_LEARNING_BIN_TREE_HPP
#include "bin_node.hpp"
#include <iostream>
#include <stdlib.h>

#define max(a,b) ((a)>(b)?(a):(b))

template <typename T>
class BinTree{
protected:
    int _size;
    BinNodePosi(T) _root;   //根节点
    // 更新某个节点的高度
    virtual int updateHeight(BinNodePosi(T) px);
    // 更新某个节点的高度及其以上节点的高度
    void updateHeightAbove(BinNodePosi(T) px);

public:
    BinTree():_size(0),_root(NULL){}
    ~BinTree(){
        if (_size > 0){
            remove(_root);
        }
    }

    int size()const{
        return _size;
    }

    bool empty()const{
        return !_root;
    }
    // 把某个值作为根节点插入
    BinNodePosi(T) insertAsRoot(T const&e);
    // 把一个值作为某个节点的左节点插入
    BinNodePosi(T) insertAsLC(BinNodePosi(T) px, T const&e);
    BinNodePosi(T) insertAsRC(BinNodePosi(T) px, T const&e);
    // 把一个树作为某个节点的左节点插入
    BinNodePosi(T) attachAsRC(BinNodePosi(T) px, BinTree<T>* &tree);
    BinNodePosi(T) attachAsLC(BinNodePosi(T) px, BinTree<T>* &tree);
    // 删除二叉树位置x的节点及其后代，返回被删除的节点数值
    int remove(BinNodePosi(T) xp);
    int removeAt(BinNode<T> *xp);
    BinTree<T>* secede(BinNodePosi(T) xp);

    template<typename VST>
    void travLevel( VST& visit){
        if(_root){
            _root->travLevel(visit);
        }
    }
    template<typename VST>
    void travPre( VST& visit){
        if(_root){
            _root->travPre(visit);
        }
    }

    template<typename VST>
    void travIn( VST& visit){
        if(_root){
            _root->travIn(visit);
        }
    }

    template<typename VST>
    void travPost( VST& visit){
        if(_root){
            _root->travPost(visit);
        }
    }

    bool operator< (BinTree<T> const &t){
        return _root && t._root && (_root < t._root);
    }

    bool operator==(BinTree<T> const &t){
        return _root && t._root && (_root == t._root);
    }
};
template <typename T>
int BinTree<T>::updateHeight(BinNode<T> *px) {
    return px->height = 1 + max(stature(px->lc), stature(px->rc));
}

template <typename T>
void BinTree<T>::updateHeightAbove(BinNode<T> *px)  {
    while (px){
        updateHeight(px);
        px = px->parent;
    }
}

template <typename T>
BinTree<T>* BinTree<T>::secede(BinNodePosi(T) xp){
    FromParentTo(*xp) = NULL;
    updateHeightAbove(xp->parent);

    BinTree<T>* tree = new BinTree<T>();
    tree->_root = xp;
    xp->parent = NULL;
    tree->_size = xp->size();
    _size -= tree->_size;
    return tree;
}

template <typename T>
BinNode<T> * BinTree<T>::insertAsRoot(const T &e) {
    _root = new BinNode<T>(e);
    _size = 1;
    return _root;
}

template <typename T>
BinNode<T> * BinTree<T>::insertAsLC(BinNode<T> *px, const T &e) {
     px->insertAsLC(e);
     _size ++;
     updateHeightAbove(px);
    return px->lc;
}

template <typename T>
BinNode<T> * BinTree<T>::insertAsRC(BinNode<T> *px, const T &e) {
    px->insertAsRC(e);
    _size ++;
    updateHeightAbove(px);
    return px->rc;
}

template <typename T>
BinNode<T> * BinTree<T>::attachAsLC(BinNode<T> *px, BinTree<T> *&tree) {
    px->lc = tree->_root;
    if(px->lc != NULL){
        px->lc->parent = px;
    }

    _size += tree->_size;
    updateHeightAbove(px);

    tree->_root = NULL;
    tree->_size = 0;
    tree = NULL;

    return px;
}

template <typename T>
BinNode<T> * BinTree<T>::attachAsRC(BinNode<T> *px, BinTree<T> *&tree) {
    px->rc = tree->_root;
    if(px->rc != NULL){
        px->rc->parent = px;
    }

    _size += tree->_size;
    updateHeightAbove(px);

    tree->_root = NULL;
    tree->_size = 0;
    tree = NULL;

    return px;
}

template <typename T>
int BinTree<T>::remove(BinNode<T> *xp) {
    if(xp == NULL){
        return 0;
    }
    FromParentTo(*xp) = NULL;
    updateHeightAbove(xp->parent);

    int n = removeAt(xp);
    _size -= n;
    return n;

}

// 删除二叉树中位置x处的节点及其后代, 返回被删除的节点的数值
template <typename T>
int BinTree<T>::removeAt(BinNode<T> *xp) {
    if(xp == NULL){
        return 0;
    }

    int n = 1 + removeAt(xp->lc) + removeAt(xp->rc);
    delete xp;
    return n;

}


#endif //CPP_LEARNING_BIN_TREE_HPP
